from python.mypackage import TreeNode

class Solution:
    """
    方法：递归查找最近公共祖先
    
    Args:
        root: 二叉树的根节点
        p: 第一个目标节点
        q: 第二个目标节点
        
    Returns:
        TreeNode: p和q的最近公共祖先节点
        
    Time: O(n)，其中n是二叉树中的节点数，最坏情况下需要遍历整棵树
    
    Space: O(h)，其中h是二叉树的高度，递归调用栈的空间
    """
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root in (None, p, q):
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:
            return root
        return left or right
    
    """
    方法：lowestCommonAncestor1 使用父指针查找最近公共祖先
    
    通过DFS构建每个节点到其父节点的映射，然后从p节点开始向上遍历并记录访问过的节点。
    接着从q节点开始向上遍历，第一个在p的路径中出现的节点即为最近公共祖先。
    
    Args:
        root: 二叉树的根节点
        p: 第一个目标节点
        q: 第二个目标节点
        
    Returns:
        TreeNode: p和q的最近公共祖先节点
        
    Time: O(n)，其中n是二叉树中的节点数，需要遍历整棵树构建父指针映射
    
    Space: O(n)，存储父指针映射和访问记录需要O(n)的空间
    """
    def lowestCommonAncestor1(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        parent = {}
        visited = set()
        def dfs(root):
            if root.left is not None:
                parent[root.left.val] = root
                dfs(root.left)
            
            if root.right is not None:
                parent[root.right.val] = root
                dfs(root.right)
            
        dfs(root)
        
        while p is not None:
            visited.add(p.val)
            p = parent.get(p.val)
        
        while q is not None:
            if q.val in visited:
                return q
            q = parent.get(q.val)
        
        return None